package com.atguigu.algorithm;

import lombok.extern.slf4j.Slf4j;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @author 顾遥
 */
@Slf4j
public class HorseChessboard {

    /**
     * 棋盘行数
     */
    private final int X;
    /**
     * 棋盘列数
     */
    private final int Y;

    /**
     * 访问数组
     */
    private final boolean[][] visited;
    /**
     * 棋盘
     */
    private final int[][] chessboard;

    private boolean finished;

    public HorseChessboard(int x, int y) {
        X = x;
        Y = y;
        visited = new boolean[X][Y];
        chessboard = new int[X][Y];
    }

    public static void main(String[] args) {
        int x = 9;
        int y = 9;
        int row = 1;
        int column = 1;
        HorseChessboard horseChessboard = new HorseChessboard(x, y);


        long start = System.currentTimeMillis();
        horseChessboard.traversalChessboard(row, column);
        long end = System.currentTimeMillis();

        long time = end - start;
        // 未优化 9770 ms， 优化 12 ms
        log.info("优化耗时：{} ms，即 {} s", time, time / 1000);
        System.out.println("========================棋盘======================");
        horseChessboard.show();

    }


    /**
     * 完成骑士周游
     *
     * @param row    当前行
     * @param column 当前列
     */
    public void traversalChessboard(int row, int column) {
        traversalChessboard(row - 1, column - 1, 1);
    }

    /**
     * 完成骑士周游
     *
     * @param row    当前行
     * @param column 当前列
     * @param step   当前步数
     */
    private void traversalChessboard(int row, int column, int step) {
        chessboard[row][column] = step;
        visited[row][column] = true;
        // 遍历下各个位置集合，sort 为优化排序，对小的进行优先搜索
        for (Point point : sort(next(new Point(row, column)))) {
            if (!visited[point.x][point.y]) {
                traversalChessboard(point.x, point.y, step + 1);
            }
        }
        // 没有满足条件回溯
        if (step < X * Y && !finished) {
            chessboard[row][column] = 0;
            visited[row][column] = false;
        } else {
            finished = true;
        }

    }

    public void show() {
        for (int[] row : chessboard) {
            System.out.println(Arrays.toString(row));
        }
    }

    /**
     * 马走日的集合步数
     */
    private final int[] CAN_X = new int[8];
    private final int[] CAN_Y = new int[8];

    {
        int[] can = {-2, -1, 1, 2};
        int c = 0;
        for (int j : can) {
            for (int k : can) {
                if (Math.abs(j) != Math.abs(k)) {
                    CAN_X[c] = j;
                    CAN_Y[c++] = k;
                }
            }
        }
    }

    /**
     * 根据当前位置，计算可以走那些位置，放入 ArrayList 中
     *
     * @param curPoint 当前位置
     * @return 可走位置的 ArrayList
     */
    public ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> points = new ArrayList<>();

        Point p1 = new Point();


        // 模拟下一步可走位置
        for (int i = 0; i < CAN_X.length; i++) {
            if ((p1.x = curPoint.x + CAN_X[i]) >= 0 && (p1.y = curPoint.y + CAN_Y[i]) >= 0 && p1.x < X && p1.y < Y) {
                points.add(new Point(p1));
            }
        }
        return points;
    }

    /**
     * 根据当前这一步所有的下一步选择位置，进行非递减排序
     */
    public ArrayList<Point> sort(ArrayList<Point> points){
        points.sort(Comparator.comparingInt(p -> next(p).size()));
        return points;
    }
}
